﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm
{
    class MagicStrings2
    {
        public MagicStrings2()
        {
            int testCase = Int32.Parse(TestConsole.ReadLine());
            while (testCase-- > 0)
            {
                string inputString = TestConsole.ReadLine().Trim();
                int[,] dataBoard = new int[inputString.Length, inputString.Length];
                List<int[]> result = new List<int[]>();
                result.Add(new int[3] { 0, 0, 0 });
                //입력
                for (int i = 0; i < inputString.Length; i++)
                {
                    for (int j = 0; j < inputString.Length; j++)
                    {
                        if (i + j > inputString.Length - 1)
                        { continue; }
                        if (inputString[i] > inputString[inputString.Length - 1 - j])
                        {
                            dataBoard[i, j] = 1;
                        }
                        else if (inputString[i] < inputString[inputString.Length - 1 - j])
                        {
                            dataBoard[i, j] = -1;
                        }
                        else
                        {
                            dataBoard[i, j] = 0;
                        }
                    }
                }
                //1차 처리 - 가장 긴 word 찾기
                SearchBoxBestLong(0, 0, dataBoard, result, inputString.Length, 1, 1);
                //1차 처리 - 알파뱃순으로 맨 위의 word 찾기
                
                Console.WriteLine("");
            }
        }

        public void SearchBoxBestLong(int startX, int startY, int[,] dataBoard, List<int[]> result, int wordLength, int odd, int deep)
        {
            odd *= -1;
            //대각선 방향으로 탐색
            bool findResult = false;
            for (int i = 0; i < wordLength - startX - startY; i++)
            {
                for (int j = 0; j <= i; j++)
                {
                    int x = startX + j;
                    int y = startY + i - j;
                    if (dataBoard[x, y] == odd)
                    {
                        //longWordQueue.Enqueue(new int[3] { deep, x, y });
                        if (deep == 1)
                        {
                            result.Add(new int[3] { deep, x, y });
                        }
                        else
                        {
                            //AdjustPoint(result[deep - 2][1], result[deep - 2][2], result[deep][1], result[deep][2], deep, dataBoard, inputString, 
                        }
                        findResult = true;
                        SearchBoxBestLong(x + 1, y + 1, dataBoard, result, wordLength, odd, ++deep);
                    }
                }
                if (findResult)
                { break; }
                else if (i == wordLength - startX - startY - 1)  //result가 하나도 없을 경우
                {
                    for (int j = 0; j <= i; j++)
                    {
                        int x = startX + j;
                        int y = startY + i - j;
                        //longWordQueue.Enqueue(new int[3] { -1, x, y });
                    }
                }
            }
        }


        private void AdjustPoint(int startX, int startY, int endX, int endY, int odd, int[,] dataBoard, string inputString, int minValue, out int xout, out int yout)
        {
            xout = -1;
            yout = -1;
            for (int x = startX; x <= endX; x++)
            {
                for (int y = startY; y <= endY; y++)
                {
                    if (dataBoard[x, y] == odd && inputString[x] < minValue)
                    {
                        minValue = inputString[x];
                        xout = x;
                        yout = y;
                    }
                }
            }
        }
    }
}
